<!DOCTYPE  html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"/><title>Learning to Extract and Use ASNs in Hostnames</title><meta name="author" content="Matthew Luckie, Alexander Marder, Marianne Fletcher, Bradley Huffaker, and k claffy"/><meta name="keywords" content="Regular expression learning, Internet topology"/><meta name="description" content="-  Networks  -&gt;  Naming and addressing."/><style type="text/css"> * {margin:0; padding:0; text-indent:0; }
 h1 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 17pt; }
 .s1 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 12pt; }
 .s3 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10pt; }
 h2 { color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 11pt; }
 .p, p { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; margin:0pt; }
 h3 { color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 9pt; }
 .s4 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; }
 h4 { color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 8pt; }
 .s5 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s6 { color: black; font-family:"Book Antiqua", serif; font-style: italic; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s7 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .a, a { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; }
 .s8 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 7pt; }
 .s9 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 7pt; }
 .s10 { color: black; font-family:"Book Antiqua", serif; font-style: italic; font-weight: normal; text-decoration: none; font-size: 7pt; }
 .s11 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 7pt; }
 .s12 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s14 { color: #0F732C; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s17 { color: #FB0106; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s18 { color: black; font-family:"Book Antiqua", serif; font-style: italic; font-weight: normal; text-decoration: none; font-size: 9pt; }
 .s19 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; }
 .s20 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s21 { color: #0F732C; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s22 { color: #FB0106; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s23 { color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 7pt; }
 .s24 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 7pt; }
 .s25 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; }
 .s26 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: 3pt; }
 .s27 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: 3pt; }
 .s28 { color: #0F732C; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: 3pt; }
 .s29 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: 5pt; }
 .s30 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: 5pt; }
 .s31 { color: #0F732C; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: 5pt; }
 .s32 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: -4pt; }
 .s33 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: -4pt; }
 .s34 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: -5pt; }
 .s35 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: -5pt; }
 .s36 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8.5pt; }
 .s38 { color: black; font-family:Georgia, serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; }
 .s39 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; }
 .s40 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: 5pt; }
 .s41 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 8pt; vertical-align: 5pt; }
 .s42 { color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 9pt; }
 li {display: block; }
 #l1 {padding-left: 0pt; }
 #l1> li>*:first-child:before {content: "• "; color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; }
 li {display: block; }
 #l2 {padding-left: 0pt;counter-reset: d1 1; }
 #l2> li>*:first-child:before {counter-increment: d1; content: counter(d1, decimal)" "; color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 11pt; }
 #l2> li:first-child>*:first-child:before {counter-increment: d1 0;  }
 #l3 {padding-left: 0pt;counter-reset: d2 1; }
 #l3> li>*:first-child:before {counter-increment: d2; content: "("counter(d2, decimal)") "; color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 9pt; }
 #l3> li:first-child>*:first-child:before {counter-increment: d2 0;  }
 #l4 {padding-left: 0pt;counter-reset: e1 2; }
 #l4> li>*:first-child:before {counter-increment: e1; content: counter(e1, decimal)" "; color: black; font-style: normal; font-weight: normal; text-decoration: none; }
 #l4> li:first-child>*:first-child:before {counter-increment: e1 0;  }
 #l5 {padding-left: 0pt;counter-reset: e2 1; }
 #l5> li>*:first-child:before {counter-increment: e2; content: counter(e1, decimal)"."counter(e2, decimal)" "; color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 11pt; }
 #l5> li:first-child>*:first-child:before {counter-increment: e2 0;  }
 #l6 {padding-left: 0pt;counter-reset: f1 1; }
 #l6> li>*:first-child:before {counter-increment: f1; content: "("counter(f1, lower-latin)") "; color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 7pt; }
 #l6> li:first-child>*:first-child:before {counter-increment: f1 0;  }
 #l7 {padding-left: 0pt;counter-reset: g1 3; }
 #l7> li>*:first-child:before {counter-increment: g1; content: counter(g1, decimal)" "; color: black; font-style: normal; font-weight: normal; text-decoration: none; }
 #l7> li:first-child>*:first-child:before {counter-increment: g1 0;  }
 #l8 {padding-left: 0pt;counter-reset: g2 1; }
 #l8> li>*:first-child:before {counter-increment: g2; content: counter(g1, decimal)"."counter(g2, decimal)" "; color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 11pt; }
 #l8> li:first-child>*:first-child:before {counter-increment: g2 0;  }
 #l9 {padding-left: 0pt;counter-reset: f1 2; }
 #l9> li>*:first-child:before {counter-increment: f1; content: "("counter(f1, lower-latin)") "; color: black; font-family:"Palatino Linotype", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 7pt; }
 #l9> li:first-child>*:first-child:before {counter-increment: f1 0;  }
 li {display: block; }
 #l10 {padding-left: 0pt;counter-reset: h1 6; }
 #l10> li>*:first-child:before {counter-increment: h1; content: "["counter(h1, decimal)"] "; color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 7pt; }
 #l10> li:first-child>*:first-child:before {counter-increment: h1 0;  }
 li {display: block; }
 #l11 {padding-left: 0pt;counter-reset: i1 1; }
 #l11> li>*:first-child:before {counter-increment: i1; content: "["counter(i1, decimal)"] "; color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 7pt; }
 #l11> li:first-child>*:first-child:before {counter-increment: i1 0;  }
 li {display: block; }
 #l12 {padding-left: 0pt;counter-reset: j1 8; }
 #l12> li>*:first-child:before {counter-increment: j1; content: "["counter(j1, decimal)"] "; color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 7pt; }
 #l12> li:first-child>*:first-child:before {counter-increment: j1 0;  }
 table, tbody {vertical-align: top; overflow: visible; }
</style></head><body><h1 style="padding-top: 5pt;padding-left: 73pt;text-indent: 0pt;text-align: center;">Learning to Extract and Use ASNs in Hostnames</h1><p class="s1" style="padding-top: 10pt;padding-left: 73pt;text-indent: 0pt;text-align: center;">Matthew Luckie <a href="mailto:mjl@wand.net.nz" class="s3" target="_blank">University of Waikato mjl@wand.net.nz</a></p><p class="s1" style="padding-top: 10pt;padding-left: 49pt;text-indent: 0pt;text-align: center;">Alexander Marder <a href="mailto:amarder@caida.org" class="s3" target="_blank">CAIDA, UC San Diego </a><a href="mailto:der@caida.org" class="s3" target="_blank">amarder@caida.org</a></p><p class="s1" style="padding-top: 10pt;padding-left: 49pt;text-indent: 2pt;text-align: justify;">Marianne Fletcher <a href="mailto:mfletche@wand.net.nz" class="s3" target="_blank">University of Waikato mfletche@wand.net.nz</a></p><p style="text-indent: 0pt;text-align: left;"><br/></p><h2 style="padding-left: 5pt;text-indent: 0pt;text-align: left;"><a name="bookmark0">ABSTRACT</a></h2><p class="s1" style="padding-top: 8pt;padding-left: 5pt;text-indent: 0pt;text-align: center;">Bradley Huffaker <a href="mailto:bradley@caida.org" class="s3" target="_blank">CAIDA, UC San Diego </a><a href="mailto:y@caida.org" class="s3" target="_blank">bradley@caida.org</a></p><p class="s1" style="padding-top: 8pt;padding-left: 73pt;text-indent: 0pt;text-align: center;">k claffy</p><p style="padding-left: 73pt;text-indent: 0pt;text-align: center;"><a href="mailto:kc@caida.org" class="s3" target="_blank">CAIDA, UC San Diego kc@caida.org</a></p><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;">We present the design, implementation, evaluation, and validation of a system that learns regular expressions (regexes) to extract Au- tonomous System Numbers (ASNs) from hostnames associated with router interfaces. We train our system with ASNs inferred by Router- ToAsAssignment and bdrmapIT using topological constraints from traceroute paths, as well as ASNs recorded by operators in Peer- ingDB, to learn regexes for 206 different suffixes. Because these methods for inferring router ownership can infer the wrong ASN, we modify bdrmapIT to integrate this new capability to extract ASNs from hostnames. Evaluating against ground truth, our modi- fication correctly distinguished stale from correct hostnames for 92.5% of hostnames with an ASN different from bdrmapIT’s ini- tial inference. This modification allowed bdrmapIT to increase the agreement between extracted and inferred ASNs for these routers in the January 2020 ITDK from 87.4% to 97.1% and reduce the error rate from 1/7.9 to 1/34.5. This work opens a broader horizon of opportunity for evidence-based router ownership inference.</p><h2 style="padding-top: 7pt;padding-left: 5pt;text-indent: 0pt;text-align: left;">CCS CONCEPTS</h2><ul id="l1"><li><h3 style="padding-left: 11pt;text-indent: -5pt;text-align: left;">Networks <span class="s4">→ </span>Naming and addressing<span class="p">.</span></h3></li></ul><h2 style="padding-top: 7pt;padding-left: 5pt;text-indent: 0pt;text-align: left;">KEYWORDS</h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;">Regular expression learning, Internet topology</p><h4 style="padding-top: 4pt;padding-left: 5pt;text-indent: 0pt;text-align: left;">ACM Reference Format:</h4><p class="s5" style="padding-left: 5pt;text-indent: 0pt;text-align: justify;">Matthew Luckie, Alexander Marder, Marianne Fletcher, Bradley Huffaker, and k claffy. 2020. Learning to Extract and Use ASNs in Hostnames. In <span class="s6">ACM Internet Measurement Conference (IMC ’20), October 27–29, 2020, Virtual Event, USA. </span><a href="#bookmark32" class="s7">ACM, New York, NY, USA, </a><a href="https://doi.org/10.1145/3419394.3423639" class="s7" target="_blank">7 pages. https://doi.org/10.1145/ 3419394.3423639</a></p><ol id="l2"><li><h2 style="padding-top: 9pt;padding-left: 22pt;text-indent: -16pt;text-align: left;"><a name="bookmark1">INTRODUCTION</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark44" class="a">Identifying the Autonomous System (AS) that operates a router is critical to understand connectivity within and between organiza- tions. For example, recent work has examined patterns of conges- tion between ASes [</a><a href="#bookmark46" class="a">5, </a><a href="#bookmark70" class="a">9, </a><a href="#bookmark71" class="a">34], connectivity of cloud providers [</a><a href="#bookmark72" class="a">35, </a>36],</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 1pt;text-align: left;"><span><img width="326" height="1" alt="image" src="learning_extract_use_asns_files/Image_001.png"/></span></p><p style="padding-top: 1pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;"><a href="mailto:permissions@acm.org" class="s9" target="_blank">Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from </a><a href="mailto:ermissions@acm.org" class="s9" target="_blank">permissions@acm.org.</a></p><p class="s10" style="padding-left: 5pt;text-indent: 0pt;text-align: left;">IMC ’20, October 27–29, 2020, Virtual Event, USA</p><p class="s11" style="padding-left: 5pt;text-indent: 0pt;text-align: left;">© <span class="s8">2020 Association for Computing Machinery. ACM ISBN 978-1-4503-8138-3/20/10. . . $15.00</span></p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 8pt;text-align: left;"><a href="https://doi.org/10.1145/3419394.3423639" class="s9">https://doi.org/10.1145/3419394.3423639</a></p><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="text-indent: 0pt;text-align: left;"><span><img width="300" height="164" alt="image" src="learning_extract_use_asns_files/Image_002.png"/></span></p><p class="s12" style="padding-left: 42pt;text-indent: 0pt;text-align: left;">Router<span class="s5"> </span>#1:<span class="s5"> </span>Inferred<span class="s5"> </span>AS<span class="s5"> </span><span style=" color: #0F732C;">15133</span><span class="s14"> </span>(<span style=" color: #002EFF;">Edgecast</span>)</p><p class="s12" style="padding-left: 38pt;text-indent: 0pt;text-align: left;">as<span style=" color: #0F732C;">15133</span>.cr2-nyc6.ip4.gtt.net<span class="s5"> </span>3257<span class="s5"> </span>173.205.63.202</p><p class="s12" style="padding-left: 6pt;text-indent: 0pt;text-align: left;"><span style=" color: #002EFF;">edgecast</span>-ic-317659-nyk-b5.c.telia.net<span class="s5"> </span>1299<span class="s5"> </span>62.115.147.199</p><p class="s12" style="padding-left: 3pt;text-indent: 0pt;text-align: left;"><span style=" color: #002EFF;">edgecast</span>.newyork51.new.seabone.net<span class="s5"> </span>6762<span class="s5"> </span>195.22.195.27</p><p class="s12" style="padding-top: 5pt;padding-left: 46pt;text-indent: 0pt;text-align: left;">Router<span class="s5"> </span>#2:<span class="s5"> </span>Inferred<span class="s5"> </span>AS<span class="s5"> </span><span style=" color: #0F732C;">3491</span><span class="s14"> </span>(<span style=" color: #002EFF;">PCCW</span>)</p><p class="s12" style="padding-top: 1pt;padding-left: 66pt;text-indent: 0pt;text-align: left;">as<span style=" color: #0F732C;">3491</span>.ip4.gtt.net<span class="s5"> </span>3257<span class="s5"> </span>77.67.94.154</p><p class="s12" style="padding-left: 12pt;text-indent: 0pt;text-align: left;"><span style=" color: #002EFF;">pccw</span>-ic-319977-ldn-b3.c.telia.net<span class="s5"> </span>1299<span class="s5"> </span>213.248.68.105</p><p class="s12" style="padding-left: 15pt;text-indent: 0pt;text-align: left;">be2-132.br02.ldn12.pccwbtn.net<span class="s5"> </span>3491<span class="s5"> </span>63.218.52.253</p><p class="s12" style="padding-top: 5pt;padding-left: 50pt;text-indent: 0pt;text-align: left;">Router<span class="s5"> </span>#3:<span class="s5"> </span>Inferred<span class="s5"> </span>AS<span class="s5"> </span><span style=" color: #FB0106;">6461</span><span class="s17"> </span>(Zayo)</p><p class="s12" style="padding-top: 1pt;padding-left: 30pt;text-indent: 0pt;text-align: left;">as<span style=" color: #FB0106;">2914</span>.cr3-lax1.ip4.gtt.net<span class="s5"> </span>3257<span class="s5"> </span>216.221.157.90</p><p class="s12" style="padding-left: 20pt;text-indent: 0pt;text-align: left;">ae3.er2.lga5.us.zip.zayo.com<span class="s5"> </span>6461<span class="s5"> </span>64.125.14.5</p><p style="text-indent: 0pt;text-align: left;"/><p class="s12" style="padding-top: 4pt;padding-left: 67pt;text-indent: 0pt;text-align: left;"><a name="bookmark2">gtt.net</a><span class="s5"> </span>regex:<span class="s5"> </span>^as<span style=" color: #0F732C;">(\d+)</span>\..+\.gtt\.net$</p><p style="text-indent: 0pt;text-align: left;"><br/></p><h3 style="padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: justify;">Figure 1: Border routers with interface IP addresses routed and named by their supplying AS. These hostnames allow researchers and operators to reason about router-level inter- domain connectivity.</h3><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark45" class="a">macroscopic impacts of submarine cable deployments [</a><a href="#bookmark63" class="a">8], and load balanced paths within and between ASes [</a><a href="#bookmark65" class="a">27, </a><a href="#bookmark49" class="a">29]. Because there is no database that stores the AS that operates every router, re- searchers have developed and refined heuristic-based methods to infer the AS that operates a router using topological constraints from traceroute and BGP paths [</a><a href="#bookmark55" class="a">12, </a><a href="#bookmark58" class="a">18, </a><a href="#bookmark59" class="a">21, </a><a href="#bookmark61" class="a">22, </a><a href="#bookmark62" class="a">24–</a>26]. However, router-level Internet connectivity is complex, techniques for infer- ring router-level connectivity have limited capability, and obtaining ground truth at scale to inform heuristic development is difficult, restricting the accuracy of these methods.</p><p style="padding-left: 5pt;text-indent: 10pt;line-height: 106%;text-align: justify;"><a href="#bookmark2" class="a">To aid network management, some network operators encode the AS that operates a router in DNS hostname strings. This AS annotation is important for attribution, as when two ASes inter- connect, one AS supplies an IP address to its neighbor to facilitate connectivity. This IP address is registered to the supplying AS in WHOIS, and typically originated in BGP by the supplying AS, so naïve interpretations of who operates a router that use these sources of data can mislead operators and researchers. Figure </a><a href="#bookmark61" class="a">1 provides examples of border routers with interface IP addresses routed and named by their supplying AS, as well as the ASNs that one heuristic-based method, bdrmapIT [</a>24], inferred for the routers. The operators supplying IP addresses for these router interfaces have different conventions for assigning hostnames to these IP addresses; gtt.net embeds the ASN, while telia.net and seabone.net embed the <span class="s18">AS name</span>. In this paper, we implement a method to au- tomatically learn regular expressions (regexes) that extract these ASN annotations. This paper makes four contributions:</p><p style="text-indent: 0pt;text-align: left;"><br/></p><ol id="l3"><li><h3 style="padding-left: 5pt;text-indent: 10pt;line-height: 11pt;text-align: justify;">We introduce and validate a method that infers regexes that extract AS numbers from hostnames. <a href="#bookmark56" class="a">Our method finds patterns in hostnames that embed an ASN, including necessary literals and character classes in regexes that capture these patterns. We validated our inferred regexes with five operators, who reported that we captured their naming intent, though in one case our regex was too specific because of stale hostnames. We implemented our method in the Hoiho tool [</a><a href="#bookmark53" class="a">19], and publicly release our source code implementation as part of scamper </a><a href="#bookmark53">[16].</a></h3></li><li><h3 style="padding-left: 5pt;text-indent: 10pt;line-height: 94%;text-align: justify;">We demonstrate the utility of our algorithm by apply- ing it to 19 sets of training data across 10 years. <a href="#bookmark40" class="a">We used the 17 Internet Topology Data Kit (ITDK [</a><span class="p">1]) snapshots built by CAIDA</span></h3><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark49" class="a">between July 2010 and January 2020 that include routers anno- tated with AS inferences using the RouterToAsAssignment [</a><a href="#bookmark61" class="a">12] (2010–2017) or bdrmapIT [</a><a href="#bookmark57" class="a">24] (2017–2020) heuristic-based router ownership inference methods – as well as two PeeringDB snap- shots – to build regexes for 206 suffixes. We publicly release the training data and inferred regexes on a website that shows how these regexes applied to training data </a><a href="#bookmark57">[20].</a></p></li><li><h3 style="padding-left: 5pt;text-indent: 9pt;line-height: 90%;text-align: justify;">We modify bdrmapIT to evaluate extracted ASNs when inferring router ownership. <span class="p">We consider the possibilities that</span></h3><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark2" class="a">the hostname is stale, or the bdrmapIT-inferred AS was wrong (con- sider the discrepancy for the third router in figure </a><a href="#bookmark60" class="a">1). We extend bdrmapIT to consider the extracted ASNs in the context of the topo- logical constraints it gathers when inferring the AS that operates a router. For the January 2020 ITDK, our modification distinguished stale from correct hostnames for 92.5% of hostnames incongruent with bdrmapIT’s initial inference, increasing agreement between the extracted and inferred ASNs from 87.4% to 97.1% and reduce the error rate from 1/7.9 to 1/34.5 for these routers. We publicly release our modifications to bdrmapIT </a><a href="#bookmark60">[23].</a></p></li><li><h3 style="padding-left: 5pt;text-indent: 9pt;line-height: 10pt;text-align: justify;">We establish a new source of validation data for router-</h3><h3 style="padding-left: 5pt;text-indent: 0pt;line-height: 11pt;text-align: justify;">level interconnection mapping. <a href="#bookmark6" class="a">Obtaining ground truth at scale is fundamentally intractable; prior work </a><span class="p">(§2.1) validated methods on at most 7 networks, mostly Tier-1 and R&amp;E networks, triggering concerns about generalizability of methods. We inferred 90 regexes from the January 2020 ITDK for networks of diverse geography, size, and class, offering future methods a promising approach to validation data that can be shared.</span></h3><p style="text-indent: 0pt;text-align: left;"><br/></p></li></ol></li><li><h2 style="padding-left: 22pt;text-indent: -16pt;text-align: left;"><a name="bookmark3">BACKGROUND AND RELATED WORK</a><a name="bookmark4">&zwnj;</a><a name="bookmark6">&zwnj;</a><a name="bookmark7">&zwnj;</a></h2><ol id="l4"><ol id="l5"><li><h2 style="padding-left: 30pt;text-indent: -24pt;text-align: left;">Inferring Router Ownership</h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;">In 2003, Mao <span class="s18">et al. </span><a href="#bookmark59" class="a">developed heuristics to improve IP-to-AS map- pings for router interfaces [</a><a href="#bookmark2" class="a">22], changing IP-to-AS mappings de- rived from BGP routing so that traceroute-inferred AS paths were more congruent with BGP AS paths for corresponding prefixes. They used hostnames to infer the AS for named but unrouted in- terfaces, assigning the same AS mapping as a neighboring routed interface with the same suffix. However, this heuristic is unreli- able because the supplying AS assigns hostnames to the IPs they provide to their neighbor for interconnection (figure </a>1). In 2004, Mao <span class="s18">et al. </span><a href="#bookmark58" class="a">used a dynamic programming technique to change IP- to-AS mappings at a /24 prefix granularity using co-located BGP and traceroute views [</a>21]. However, operators typically use /30 or</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;">/31 prefixes (rather than /24s) for private interconnection between networks to use address space efficiently.</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="padding-left: 5pt;text-indent: 10pt;line-height: 106%;text-align: justify;">In 2010, Huffaker <span class="s18">et al. </span><a href="#bookmark49" class="a">evaluated router ownership heuristics that used router alias resolution, AS relationships, and degrees [</a>12]. The best-performing heuristic they evaluated was to choose the AS that announced the longest matching prefix for the most interfaces on the router in BGP (election), breaking ties by choosing the smaller of the ASes with interfaces on the router (degree). They validated using data from a Tier-1 network, a Tier-2 network, as well as five research and education networks, and reported that 80% of the AS inferences were correct when the inferred routers had interfaces from multiple ASes, but reduced to 71% when including routers with interfaces in a single AS, likely because traceroute usually only observes the provider-supplied (and BGP-announced) address for border routers of stub ASes. They publicly released their source code implementation, which they called RouterToAsAssignment. Twelve ITDKs built between July 2010 and February 2017 used this technique to infer router ownership.</p><p style="padding-left: 15pt;text-indent: 0pt;line-height: 10pt;text-align: justify;">In 2016, Luckie <span class="s18">et al. </span>and Marder <span class="s18">et al. </span><a href="#bookmark55" class="a">built the bdrmap [</a>18]</p><p class="s19" style="text-indent: 0pt;line-height: 9pt;text-align: left;">≈</p><p style="text-indent: 0pt;text-align: left;"/><p style="padding-left: 5pt;text-indent: 0pt;text-align: justify;"><a href="#bookmark62" class="a">and MAP-IT [</a>26] techniques, respectively. The bdrmap technique focused on finding all neighbor routers forming an interdomain link with an AS hosting a traceroute vantage point (VP), that are observ- able from that VP. From a single VP, bdrmap conducts traceroute to every routed prefix, and uses a set of heuristics in conjunction with AS relationships and BGP routing information to infer ownership of the neighbor routers. Luckie <span class="s18">et al. </span>validated bdrmap’s router ownership inferences using ground truth provided by a Tier-1 net- work, one large and one small access network, and a research and education (R&amp;E) network, reporting that 97.1% of inferred ASes corresponded to the organization operating the router. MAP-IT used a graph refinement technique to infer owners for all routers observed in the <span class="s18">middle </span>of a traceroute path, in a collection of tracer- outes. In validating MAP-IT, Marder <span class="s18">et al. </span>focused on IP addresses they inferred were used for AS interconnection for two Tier-1 networks. They manually interpreted hostnames those operators assigned, reporting that 95.0% of their interconnection inferences were correct. They also obtained ground truth from a R&amp;E network, reporting that all interconnection inferences were correct.</p><p class="s19" style="text-indent: 0pt;line-height: 9pt;text-align: left;">≈</p><p style="text-indent: 0pt;text-align: left;"/><p style="padding-left: 5pt;text-indent: 9pt;text-align: justify;">In 2018, Marder <span class="s18">et al. </span><a href="#bookmark61" class="a">built bdrmapIT [</a>24], incorporating bdrmap’s heuristics, such as those for inferring ownership of routers only observed at the edge of traceroutes where there are no adjacent routers from which to reason about ownership, with MAP-IT’s graph refinement, to extend bdrmap’s router ownership inference heuristics outside the VP network. They validated using ground truth from a Tier-1 network, a large access network, and two R&amp;E networks, reporting that 95.3% of their AS interconnection IP address inferences correctly identified the operating ASes on each side of the interconnections. Five ITDKs built between August 2017 and January 2020 used bdrmapIT to infer router ownership.</p><p style="padding-left: 5pt;text-indent: 10pt;line-height: 106%;text-align: justify;">These existing heuristic-based methods are not suitable for in- ferring ownership of routers observed in one-off or limited sets of traceroutes, as they rely on accumulating constraints from a large set of traceroutes for their accuracy. Our method allows researchers to benefit from these previous methods without requiring a large set of traceroutes. In addition, our method enables corroboration and validation of inferences made using these heuristic-based meth- ods. Importantly, since validation of previous methods has used proprietary ground truth data, our method yields validation data (hostname annotations) that can be shared.</p></li><li><h2 style="padding-top: 7pt;padding-left: 5pt;text-indent: 0pt;line-height: 107%;text-align: left;"><a name="bookmark5">Topology Information in Hostnames </a><a href="#bookmark49" class="a">Researchers and operators use hostnames in DNS pointer (PTR) records to understand router-level topology. Prior work has used these hostnames to infer and validate router ownership [</a><a href="#bookmark59" class="a">12, </a><a href="#bookmark62" class="a">22, </a><a href="#bookmark48" class="a">26], geolocation [</a><a href="#bookmark50" class="a">11, </a><a href="#bookmark67" class="a">13, </a><a href="#bookmark69" class="a">31, </a><a href="#bookmark41" class="a">33], physical properties [</a><a href="#bookmark34" class="a">2, </a><a href="#bookmark35" class="a">6, </a><a href="#bookmark47" class="a">7, </a><a href="#bookmark51" class="a">10], and which interfaces belong to the same router [</a><a href="#bookmark54" class="a">14, </a><a href="#bookmark56" class="a">17, </a><a href="#bookmark68" class="a">19, </a><span class="p">32]. Using hostnames to infer router-level properties of networks is challenging, as each operator independently decides on a naming convention for their suffix, leading researchers to manually build</span></h2></li></ol></ol><p style="text-indent: 0pt;text-align: left;"><br/></p><p class="s12" style="padding-left: 10pt;text-indent: -4pt;line-height: 109%;text-align: left;"><a name="bookmark8">training</a><span class="s5"> </span>ASN</p><p style="text-indent: 0pt;text-align: left;"><br/></p><table style="border-collapse:collapse" cellspacing="0"><tr style="height:9pt"><td style="width:34pt"><p class="s20" style="padding-left: 5pt;padding-right: 3pt;text-indent: 0pt;line-height: 8pt;text-align: center;">15576</p></td><td style="width:137pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">ge0-2.01.p.ost.ch.as<span style=" color: #0F732C;">15576</span>.nts.ch</p></td></tr><tr style="height:10pt"><td style="width:34pt"><p class="s20" style="padding-left: 5pt;padding-right: 3pt;text-indent: 0pt;line-height: 9pt;text-align: center;">15576</p></td><td style="width:137pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">lo1000.01.lns.czh.ch.as<span style=" color: #0F732C;">15576</span>.nts.ch</p></td></tr><tr style="height:10pt"><td style="width:34pt"><p class="s20" style="padding-left: 5pt;padding-right: 3pt;text-indent: 0pt;line-height: 9pt;text-align: center;">15576</p></td><td style="width:137pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">te0-0-24.01.p.bre.ch.as<span style=" color: #0F732C;">15576</span>.nts.ch</p></td></tr><tr style="height:10pt"><td style="width:34pt"><p class="s20" style="padding-left: 5pt;padding-right: 3pt;text-indent: 0pt;line-height: 9pt;text-align: center;">44879</p></td><td style="width:137pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">01.r.cba.ch.bl.cust.as<span style=" color: #FB0106;">15576</span>.nts.ch</p></td></tr><tr style="height:10pt"><td style="width:34pt"><p class="s20" style="padding-left: 5pt;padding-right: 3pt;text-indent: 0pt;line-height: 9pt;text-align: center;">51768</p></td><td style="width:137pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">02.r.czh.ch.sda.cust.as<span style=" color: #FB0106;">15576</span>.nts.ch</p></td></tr><tr style="height:9pt"><td style="width:34pt"><p class="s20" style="padding-left: 1pt;padding-right: 3pt;text-indent: 0pt;line-height: 8pt;text-align: center;">206616</p></td><td style="width:137pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">01.r.cbs.ch.wwc.cust.as<span style=" color: #FB0106;">15576</span>.nts.ch</p></td></tr></table><p style="text-indent: 0pt;text-align: left;"/><p class="s12" style="padding-left: 34pt;text-indent: 5pt;line-height: 109%;text-align: left;">hostname<span class="s5"> </span>(PTR<span class="s5"> </span>record)</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p class="s12" style="padding-left: 5pt;text-indent: 0pt;text-align: left;">as<span style=" color: #0F732C;">(\d+)</span>\.nts\.ch$</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: left;"><a href="#bookmark47" class="a">regexes to capture structure unique to each suffix [</a><a href="#bookmark49" class="a">10, </a><a href="#bookmark51" class="a">12, </a><a href="#bookmark54" class="a">14, </a><a href="#bookmark69" class="a">17, </a><a href="#bookmark73" class="a">33]. Further, hostnames can have typos and become stale </a><a href="#bookmark73">[37].</a></p><p style="padding-left: 15pt;text-indent: 0pt;line-height: 8pt;text-align: left;">More recently, researchers have applied machine learning ap-</p><h3 style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: left;">Figure 2: Example suffix that labels the AS that supplies the address, not the AS that operates the router.</h3><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;">proaches to automatically infer regexes that extract information from hostnames. In 2014, Huffaker <span class="s18">et al. </span><a href="#bookmark50" class="a">built DRoP [</a>13] to in- fer regexes that extract apparent geolocation strings from router hostnames. In 2019, Luckie <span class="s18">et al. </span><a href="#bookmark56" class="a">built the Holistic Orthography of Internet Hostname Observations (Hoiho) tool [</a>19] to infer the portion of a hostname that embeds a <span class="s18">router name </span>shared among interfaces on the same router, but unique across routers in the suffix,</p><p class="s12" style="padding-left: 5pt;text-indent: 0pt;line-height: 8pt;text-align: left;"><a name="bookmark9">training</a></p><table style="border-collapse:collapse" cellspacing="0"><tr style="height:10pt"><td style="width:49pt"><p class="s20" style="padding-right: 19pt;text-indent: 0pt;line-height: 8pt;text-align: right;">701</p></td><td style="width:163pt"><p class="s22" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">201<span style=" color: #000;">.atm2-0.vr1.tor2.alter.net</span></p></td></tr><tr style="height:10pt"><td style="width:49pt"><p class="s20" style="padding-right: 19pt;text-indent: 0pt;line-height: 9pt;text-align: right;">855</p></td><td style="width:163pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">te-4-0-0-<span style=" color: #FB0106;">85</span>.53w.ba07.mctn.nb.aliant.net</p></td></tr><tr style="height:10pt"><td style="width:49pt"><p class="s20" style="padding-right: 19pt;text-indent: 0pt;line-height: 9pt;text-align: right;">6057</p></td><td style="width:163pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">mlg4bras1-be127-<span style=" color: #FB0106;">605</span>.antel.net.uy</p></td></tr><tr style="height:10pt"><td style="width:49pt"><p class="s20" style="padding-right: 19pt;text-indent: 0pt;line-height: 9pt;text-align: right;">20940</p></td><td style="width:163pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">as<span style=" color: #0F732C;">24940</span>.akl-ix.nz</p></td></tr><tr style="height:10pt"><td style="width:49pt"><p class="s20" style="padding-right: 19pt;text-indent: 0pt;line-height: 9pt;text-align: right;">205073</p></td><td style="width:163pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">as<span style=" color: #0F732C;">202073</span>.swissix.ch</p></td></tr><tr style="height:10pt"><td style="width:49pt"><p class="s20" style="padding-right: 19pt;text-indent: 0pt;line-height: 8pt;text-align: right;">207032</p></td><td style="width:163pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">gw-as<span style=" color: #0F732C;">20732</span>.init7.net</p></td></tr></table><p style="text-indent: 0pt;text-align: left;"/><p class="s12" style="padding-left: 10pt;text-indent: 0pt;text-align: left;">ASN</p><p class="s12" style="padding-left: 34pt;text-indent: 0pt;line-height: 8pt;text-align: center;">hostname</p><p class="s12" style="padding-left: 34pt;text-indent: 0pt;text-align: center;">(PTR<span class="s5"> </span>record)</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: left;">to infer router aliases. That work learned regexes that increased in specificity and completeness over the course of eight stages, and</p><ol id="l6"><li><p class="s23" style="padding-top: 3pt;padding-left: 6pt;text-indent: 0pt;line-height: 84%;text-align: left;"><a name="bookmark10">Apparent ASNs can have an edit distance of one from their train- ing ASN, by coincidence or typo.</a></p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark56" class="a">showed that it is possible to infer likely aliases using hostnames and regexes that prior techniques missed [</a>19]. In this work, we modify Hoiho to learn to infer the portion of a hostname that em-</p><p class="s12" style="padding-left: 5pt;text-indent: 0pt;text-align: left;">122</p><p class="s12" style="padding-left: 5pt;text-indent: 0pt;text-align: left;">209</p><p class="s12" style="padding-left: 5pt;text-indent: 0pt;text-align: left;">209</p><p class="s12" style="padding-left: 35pt;text-indent: -29pt;line-height: 109%;text-align: right;">50-236-216-<span style=" color: #FB0106;">122</span>-static.hfc.comcastbusiness.net<span class="s5"> </span><span style=" color: #FB0106;">209</span>-201-58-109.dia.stat.centurylink.net<span class="s5"> </span><span style=" color: #FB0106;">209</span>-206-252-105.stat.centurytel.net</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;">beds the ASN of the network that operates the router, and introduce techniques to detect hostnames that contain stale ASN annotations, so that heuristic-based router ownership inference methods can automatically evaluate correct ASN annotations. More broadly, the measurement community will be able to more confidently charac- terize router-level Internet structure if the community is able to automatically use information encoded in hostnames.</p></li></ol></li><li><h2 style="padding-top: 9pt;padding-left: 22pt;text-indent: -16pt;text-align: left;"><a name="bookmark11">BUILDING CONVENTIONS</a><a name="bookmark18">&zwnj;</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark64" class="a">Our algorithm learns if an operator uses a naming convention (NC) that embeds an ASN in a hostname, by evaluating automatically generated candidate regexes against sets of router hostnames with the same suffix. We determine suffixes using the Mozilla public suffix list [</a>28], which lists effective top-level domains (e.g. .com,</p><p style="padding-left: 5pt;text-indent: 0pt;text-align: justify;">.org.nz) under which operators can register their own domain suf- fixes (e.g. example.com, luckie.org.nz). We annotate each router with a <span class="s18">training ASN </span><a href="#bookmark6" class="a">inferred heuristically </a><a href="#bookmark2" class="a">(§2.1) or recorded by an operator in PeeringDB. If a regex extracts different ASNs for different hostnames in the same suffix, and the extracted ASNs are congruent with training ASNs, we infer that each hostname embeds the ASN that operates the router, as we do for the example in figure </a><a href="#bookmark8" class="a">1. A regex must extract multiple different ASNs congruent with training data, because some operators embed the ASN that supplies the address, even for addresses they supply to neighbor routers, illustrated by the example in figure </a><a href="#bookmark8">2.</a></p><ol id="l7"><ol id="l8"><li><h2 style="padding-top: 9pt;padding-left: 30pt;text-indent: -24pt;text-align: left;"><a name="bookmark12">Evaluating and Ranking Regexes</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;">A hostname contains an <span class="s18">apparent ASN </span>if it contains a numeric string (number) congruent with the training ASN for the router with that hostname. Hoiho evaluates regexes using the following per-hostname classifications. Hoiho assigns a true positive (TP) when a regex extracts a number congruent with the training ASN</p><ol id="l9"><li><p class="s23" style="padding-left: 19pt;text-indent: 0pt;line-height: 84%;text-align: left;">Hostnames can embed an IP address, with portions the same as the training ASN, by coincidence.</p></li></ol><h3 style="padding-top: 6pt;padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: justify;">Figure 3: Example hostnames with apparent ASNs, which differ from the training ASN by a single digit (a), or were derived from an IP address (b).</h3><p style="padding-top: 7pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark43" class="a">for that hostname. Some hostnames contain an apparent ASN that differs from the training ASN with a Damerau-Levenshtein edit distance of one [</a><a href="#bookmark52" class="a">4, </a><a href="#bookmark9" class="a">15] possibly suggesting a typo. Figure </a><a href="#bookmark10" class="a">3a shows sample hostnames with apparent ASNs that have an edit distance of one from the training ASNs, some of which are typos, and others by coincidence. Hoiho therefore also assigns a TP when the first and last characters of the training ASN and extracted number are the same, and both numbers are at least three digits in length, to avoid inferring a TP where the training ASN and extracted number have an edit distance of one by coincidence; Hoiho found seven hostnames with typos in the January 2020 ITDK. Hoiho otherwise assigns a false positive (FP) when a regex extracts a different number than the training ASN, or when the extracted number is part of an IP address embedded in the hostname, illustrated in figure </a>3b. Finally, Hoiho assigns a false negative (FN) when a regex does not extract a number from a hostname and there is an apparent ASN in the hostname congruent with the training ASN.</p><p style="padding-left: 5pt;text-indent: 9pt;line-height: 106%;text-align: justify;"><a href="#bookmark56" class="a">Our metric for ranking regexes, which we call Absolute True Positives (ATP), is TP-(FP+FN). Our ATP metric includes FNs be- cause our goal is to find a regex that matches as many hostnames as possible, rather than find a regex that has high positive predic- tive value (PPV, TP/(TP+FP)) for a subset of interfaces. Hoiho used a different definition of ATP when it evaluated regexes to infer router names [</a>19], penalizing regexes that separated hostnames from routers (one class of FN), but did not penalize regexes that did not match routers with aliases (a second class of FN) because not all operators embed a router name in their hostnames.</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="padding-left: 173pt;text-indent: 0pt;line-height: 1pt;text-align: left;"><span><img width="441" height="1" alt="image" src="learning_extract_use_asns_files/Image_003.png"/></span></p><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="text-indent: 0pt;text-align: left;"><br/></p><p class="s12" style="padding-left: 10pt;text-indent: 0pt;text-align: left;"><a name="bookmark19">55923</a></p><p style="text-indent: 0pt;text-align: left;"><br/></p><p class="s12" style="padding-left: 10pt;text-indent: 0pt;text-align: left;"><span style=" color: #FB0106;">45437</span>-sy1-ix.equinix.com<span class="s5"> </span>(p)</p><p class="s12" style="padding-top: 3pt;padding-left: 6pt;text-indent: 0pt;text-align: left;">#6<span class="s5"> </span>^(?:p|s)?(\d+)\.[a-z\d]+\.equinix\.com$</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="text-indent: 0pt;text-align: left;"><span><img width="446" height="1" alt="image" src="learning_extract_use_asns_files/Image_004.png"/></span></p><table style="border-collapse:collapse" cellspacing="0"><tr style="height:10pt"><td style="width:43pt"><p class="s20" style="padding-left: 3pt;text-indent: 0pt;line-height: 9pt;text-align: left;">training</p></td><td style="width:122pt" colspan="2"><p class="s20" style="padding-left: 41pt;padding-right: 43pt;text-indent: 0pt;line-height: 9pt;text-align: center;">hostname</p></td><td style="width:187pt;border-bottom-style:dashed;border-bottom-width:2pt" colspan="2"><p class="s24" style="padding-right: 17pt;text-indent: 0pt;text-align: right;">TP</p></td><td style="width:26pt;border-bottom-style:dashed;border-bottom-width:2pt"><p class="s24" style="padding-left: 6pt;padding-right: 4pt;text-indent: 0pt;text-align: center;">FP</p></td><td style="width:82pt;border-bottom-style:dashed;border-bottom-width:2pt"><p class="s24" style="padding-left: 5pt;padding-right: 6pt;text-indent: 0pt;text-align: center;">FN</p></td><td style="width:43pt;border-bottom-style:dashed;border-bottom-width:2pt" colspan="2"><p class="s24" style="padding-left: 6pt;text-indent: 0pt;text-align: left;">ATP</p></td></tr><tr style="height:12pt"><td style="width:43pt"><p class="s20" style="padding-left: 8pt;text-indent: 0pt;line-height: 8pt;text-align: left;">ASN</p></td><td style="width:122pt" colspan="2"><p class="s20" style="padding-left: 36pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(PTR<span class="s25"> </span>record)</p></td><td style="width:187pt" colspan="2"><p class="s20" style="padding-top: 2pt;padding-left: 13pt;text-indent: 0pt;line-height: 8pt;text-align: left;">Phase<span class="s25"> </span>1:<span class="s25"> </span>Generate<span class="s25"> </span>Base<span class="s25"> </span>Regexes</p></td><td style="width:26pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:82pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:43pt" colspan="2"><p class="s20" style="padding-top: 2pt;padding-left: 18pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(§3.2)</p></td></tr><tr style="height:11pt"><td style="width:43pt"><p class="s20" style="padding-left: 11pt;text-indent: 0pt;line-height: 8pt;text-align: left;">109</p></td><td style="width:103pt"><p class="s21" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">109<span style=" color: #000;">.sgw.equinix.com</span></p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(a)</p></td><td style="width:134pt"><p class="s20" style="padding-top: 1pt;padding-left: 1pt;text-indent: 0pt;line-height: 8pt;text-align: left;">#1<span class="s25"> </span>^(\d+)\.[^\.]+\.equinix\.com$</p></td><td style="width:53pt"><p class="s20" style="padding-top: 1pt;padding-right: 8pt;text-indent: 0pt;line-height: 8pt;text-align: right;">a,<span class="s25"> </span>b,<span class="s25"> </span>c</p></td><td style="width:26pt"><p class="s20" style="padding-top: 1pt;padding-left: 6pt;padding-right: 4pt;text-indent: 0pt;line-height: 8pt;text-align: center;">n,<span class="s25"> </span>o</p></td><td style="width:82pt"><p class="s20" style="padding-top: 1pt;padding-left: 5pt;padding-right: 6pt;text-indent: 0pt;line-height: 8pt;text-align: center;">d,<span class="s25"> </span>e,<span class="s25"> </span>f,<span class="s25"> </span>g,<span class="s25"> </span>h,<span class="s25"> </span>i,<span class="s25"> </span>j,<span class="s25"> </span>k</p></td><td style="width:18pt"><p class="s20" style="padding-top: 1pt;padding-right: 1pt;text-indent: 0pt;line-height: 8pt;text-align: right;">-7</p></td><td style="width:25pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td></tr><tr style="height:10pt"><td style="width:43pt"><p class="s20" style="padding-left: 11pt;text-indent: 0pt;line-height: 8pt;text-align: left;">714</p></td><td style="width:103pt"><p class="s21" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">714<span style=" color: #000;">.os.equinix.com</span></p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(b)</p></td><td style="width:134pt"><p class="s20" style="padding-left: 1pt;text-indent: 0pt;line-height: 8pt;text-align: left;">#2<span class="s25"> </span>^p(\d+)\.[^\.]+\.equinix\.com$</p></td><td style="width:53pt"><p class="s20" style="padding-right: 14pt;text-indent: 0pt;line-height: 8pt;text-align: right;">d,<span class="s25"> </span>f</p></td><td style="width:26pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:82pt"><p class="s20" style="padding-left: 5pt;padding-right: 6pt;text-indent: 0pt;line-height: 8pt;text-align: center;">a,<span class="s25"> </span>b,<span class="s25"> </span>c,<span class="s25"> </span>e,<span class="s25"> </span>g,<span class="s25"> </span>h,<span class="s25"> </span>i,<span class="s25"> </span>j,<span class="s25"> </span>k</p></td><td style="width:18pt"><p class="s20" style="padding-right: 1pt;text-indent: 0pt;line-height: 8pt;text-align: right;">-7</p></td><td style="width:25pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td></tr><tr style="height:10pt"><td style="width:43pt"><p class="s20" style="padding-left: 11pt;text-indent: 0pt;line-height: 8pt;text-align: left;">714</p></td><td style="width:103pt"><p class="s21" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">714<span style=" color: #000;">.me1.equinix.com</span></p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(c)</p></td><td style="width:134pt"><p class="s20" style="padding-left: 1pt;text-indent: 0pt;line-height: 8pt;text-align: left;">#3<span class="s25"> </span>^s(\d+)\.[^\.]+\.equinix\.com$</p></td><td style="width:53pt"><p class="s20" style="padding-right: 13pt;text-indent: 0pt;line-height: 8pt;text-align: right;">e,<span class="s25"> </span>g</p></td><td style="width:26pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:82pt"><p class="s20" style="padding-left: 5pt;padding-right: 6pt;text-indent: 0pt;line-height: 8pt;text-align: center;">a,<span class="s25"> </span>b,<span class="s25"> </span>c,<span class="s25"> </span>d,<span class="s25"> </span>f,<span class="s25"> </span>h,<span class="s25"> </span>i,<span class="s25"> </span>j,<span class="s25"> </span>k</p></td><td style="width:18pt"><p class="s20" style="padding-right: 1pt;text-indent: 0pt;line-height: 8pt;text-align: right;">-7</p></td><td style="width:25pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td></tr><tr style="height:10pt"><td style="width:43pt"><p class="s20" style="padding-left: 11pt;text-indent: 0pt;line-height: 8pt;text-align: left;">714</p></td><td style="width:103pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">p<span style=" color: #0F732C;">714</span>.sgw.equinix.com</p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(d)</p></td><td style="width:134pt"><p class="s20" style="padding-left: 1pt;text-indent: 0pt;line-height: 8pt;text-align: left;">#4<span class="s25"> </span>^(\d+)-.+\.equinix\.com$</p></td><td style="width:53pt"><p class="s20" style="padding-right: 7pt;text-indent: 0pt;line-height: 8pt;text-align: right;">h,<span class="s25"> </span>i,<span class="s25"> </span>j,<span class="s25"> </span>k</p></td><td style="width:26pt"><p class="s20" style="padding-left: 1pt;text-indent: 0pt;line-height: 8pt;text-align: center;">p</p></td><td style="width:82pt"><p class="s20" style="padding-left: 5pt;padding-right: 6pt;text-indent: 0pt;line-height: 8pt;text-align: center;">a,<span class="s25"> </span>b,<span class="s25"> </span>c,<span class="s25"> </span>d,<span class="s25"> </span>e,<span class="s25"> </span>f,<span class="s25"> </span>g</p></td><td style="width:18pt"><p class="s20" style="padding-right: 1pt;text-indent: 0pt;line-height: 8pt;text-align: right;">-4</p></td><td style="width:25pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td></tr><tr style="height:9pt"><td style="width:43pt"><p class="s20" style="padding-left: 11pt;text-indent: 0pt;line-height: 7pt;text-align: left;">714</p></td><td style="width:103pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 7pt;text-align: right;">s<span style=" color: #0F732C;">714</span>.sgw.equinix.com</p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 7pt;text-align: left;">(e)</p></td><td style="width:134pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:53pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:26pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:82pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:18pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:25pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td></tr><tr style="height:10pt"><td style="width:43pt"><p class="s20" style="padding-left: 3pt;text-indent: 0pt;line-height: 8pt;text-align: left;">24115</p></td><td style="width:103pt"><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">p<span style=" color: #0F732C;">24115</span>.mel.equinix.com</p></td><td style="width:19pt"><p class="s20" style="padding-left: 3pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(f)</p></td><td style="width:134pt"><p class="s20" style="padding-left: 13pt;text-indent: 0pt;line-height: 8pt;text-align: left;">Phase<span class="s25"> </span>2:<span class="s25"> </span>Merge<span class="s25"> </span>Regexes</p></td><td style="width:53pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:26pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:82pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:18pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:25pt"><p class="s20" style="padding-left: 1pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(§3.3)</p></td></tr><tr style="height:11pt"><td style="width:503pt" colspan="9"><p class="s20" style="padding-left: 3pt;text-indent: 0pt;line-height: 9pt;text-align: left;"><span class="s26">24115</span><span class="s27"> </span><span class="s26">s</span><span class="s28">24115</span><span class="s26">.tyo.equinix.com</span><span class="s27"> </span><span class="s26">(g)</span><span class="s27"> </span>#5<span class="s25"> </span>^(?:p|s)?(\d+)\.[^\.]+\.equinix\.com$<span class="s25"> </span><span class="s29">a,</span><span class="s30"> </span><span class="s29">b,</span><span class="s30"> </span><span class="s29">c,</span><span class="s30"> </span>n,<span class="s25"> </span>o<span class="s25"> </span>h,<span class="s25"> </span>i,<span class="s25"> </span>j,<span class="s25"> </span>k<span class="s25"> </span>1</p></td></tr><tr style="height:11pt"><td style="width:43pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 9pt;text-align: left;">22282</p></td><td style="width:103pt"><p class="s21" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">22822<span style=" color: #000;">-2.tyo.equinix.com</span></p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 9pt;text-align: left;">(h)</p></td><td style="width:338pt;border-bottom-style:dashed;border-bottom-width:2pt" colspan="6"><p class="s20" style="padding-left: 152pt;padding-right: 155pt;text-indent: 0pt;line-height: 8pt;text-align: center;">d,<span class="s25"> </span>e,<span class="s25"> </span>f,<span class="s25"> </span>g</p></td></tr><tr style="height:22pt"><td style="width:503pt" colspan="9"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 11pt;text-align: left;"><span class="s29">24482</span><span class="s30"> </span><span class="s31">24482</span><span class="s29">-fr5-ix.equinix.com</span><span class="s30"> </span><span class="s29">(i)</span><span class="s30"> </span>Phase<span class="s25"> </span>3:<span class="s25"> </span>Embed<span class="s25"> </span>Character<span class="s25"> </span>Classes<span class="s25"> </span>(§3.4)</p><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 72%;text-align: left;">54827<span class="s25"> </span><span style=" color: #0F732C;">54827</span>-dc5-ix2.equinix.com<span class="s25"> </span>(j)<span class="s25"> </span><span class="s32">a,</span><span class="s33"> </span><span class="s32">b,</span><span class="s33"> </span><span class="s32">c,</span></p></td></tr></table><p style="text-indent: 0pt;text-align: left;"/><table style="border-collapse:collapse" cellspacing="0"><tr style="height:10pt"><td style="width:36pt" rowspan="2"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:110pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:19pt" rowspan="2"><p style="text-indent: 0pt;text-align: left;"><br/></p></td></tr><tr style="height:10pt"><td style="width:110pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td></tr><tr style="height:18pt"><td style="width:36pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 9pt;text-align: left;">55247</p><p class="s20" style="padding-left: 6pt;text-indent: 0pt;line-height: 7pt;text-align: left;">2906<span class="s25"> </span>n</p></td><td style="width:110pt"><p class="s21" style="padding-right: 2pt;text-indent: 0pt;line-height: 9pt;text-align: right;">55247<span style=" color: #000;">-ch3-ix.equinix.com</span></p><p class="s20" style="padding-right: 2pt;text-indent: 0pt;line-height: 7pt;text-align: right;">etﬂix.zh2.corp.eu.equinix.com</p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 9pt;text-align: left;">(k)</p><p class="s20" style="padding-left: 3pt;text-indent: 0pt;line-height: 7pt;text-align: left;">(l)</p></td></tr><tr style="height:13pt"><td style="width:165pt" colspan="3"><p class="s20" style="padding-top: 2pt;padding-left: 2pt;text-indent: 0pt;line-height: 9pt;text-align: left;">19324<span class="s25"> </span>ipv4.dosarrest.eqix.equinix.com<span class="s25"> </span>(m)</p></td></tr><tr style="height:11pt"><td style="width:36pt"><p class="s20" style="padding-left: 6pt;text-indent: 0pt;text-align: left;">8075</p></td><td style="width:110pt"><p class="s22" style="padding-right: 2pt;text-indent: 0pt;text-align: right;">8069<span style=" color: #000;">.tyo.equinix.com</span></p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;text-align: left;">(n)</p></td></tr><tr style="height:9pt"><td style="width:36pt"><p class="s20" style="padding-left: 6pt;text-indent: 0pt;line-height: 8pt;text-align: left;">8075</p></td><td style="width:110pt"><p class="s22" style="padding-right: 2pt;text-indent: 0pt;line-height: 8pt;text-align: right;">8074<span style=" color: #000;">.hkg.equinix.com</span></p></td><td style="width:19pt"><p class="s20" style="padding-left: 2pt;text-indent: 0pt;line-height: 8pt;text-align: left;">(o)</p></td></tr></table><p style="text-indent: 0pt;text-align: left;"/><p class="s12" style="padding-left: 19pt;text-indent: 0pt;text-align: left;">Phase<span class="s5"> </span>4:<span class="s5"> </span>Build<span class="s5"> </span>Regex<span class="s5"> </span>Sets</p><p class="s34" style="padding-top: 5pt;padding-left: 7pt;text-indent: 0pt;line-height: 68%;text-align: left;">#7<span class="s35"> </span><span class="s12">^(?:p|s)?(\d+)\.[a-z\d]+\.equinix\.com$</span></p><p class="s12" style="padding-left: 19pt;text-indent: 0pt;line-height: 7pt;text-align: left;">^(\d+)-.+\.equinix\.com$</p><p class="s12" style="padding-top: 3pt;padding-left: 4pt;text-indent: 0pt;text-align: left;"><span class="s34">d,</span><span class="s35"> </span><span class="s34">e,</span><span class="s35"> </span><span class="s34">f,</span><span class="s35"> </span><span class="s34">g</span><span class="s35"> </span>n,<span class="s5"> </span>o<span class="s5"> </span>h,<span class="s5"> </span>i,<span class="s5"> </span>j,<span class="s5"> </span>k<span class="s5"> </span>1</p><p class="s12" style="padding-top: 16pt;padding-left: 7pt;text-indent: 0pt;text-align: left;">a,<span class="s5"> </span>b,<span class="s5"> </span>c,</p><p class="s12" style="padding-left: 3pt;text-indent: 0pt;text-align: left;">d,<span class="s5"> </span>e,<span class="s5"> </span>f,<span class="s5"> </span>g,<span class="s5"> </span>n,<span class="s5"> </span>o,<span class="s5"> </span>p<span class="s5"> </span>8</p><p class="s12" style="padding-left: 6pt;text-indent: 0pt;text-align: left;">h,<span class="s5"> </span>i,<span class="s5"> </span>j,<span class="s5"> </span>k</p><p class="s12" style="padding-top: 25pt;padding-left: 1pt;text-indent: 0pt;text-align: left;">(§3.5)</p><h3 style="padding-top: 11pt;padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: left;">Figure 4: Inferring a naming convention (NC) for the Equinix suffix (equinix.com) across four phases. The regexes that form the NC increase in specificity and coverage through each phase.</h3></li><li><h2 style="padding-left: 30pt;text-indent: -24pt;text-align: left;"><a name="bookmark13">Generate Base Regexes</a><a name="bookmark20">&zwnj;</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;"><a href="#bookmark19" class="a">Our algorithm consists of four stages, illustrated in figure </a>4, which increase specificity and coverage as the algorithm proceeds. In the first phase, Hoiho builds base regular expressions that extract ASNs focusing on structure encoded in the hostname using punc- tuation characters. This phase recursively builds base regexes that capture the apparent ASN with (\d+) and use regex components that exclude specific punctuation depending on the punctuation at the beginning and end of each portion (e.g., [<span class="s4">^</span>\.]+ and [<span class="s4">^</span><a href="#bookmark56" class="a">-]+ match sequences of characters that do not contain a dot or hy- phen, respectively), or match anything (i.e., .+) at most once per regex, similar to prior work [</a>19]. For example, Hoiho builds <span class="s4">^</span>(\d+)- [<span class="s4">^</span>-]+-[<span class="s4">^</span>\.]+\.equinix\.com$, <span class="s4">^</span>(\d+)-[<span class="s4">^</span>-]+-[<span class="s4">^</span>-]+\.equinix\.com$, and</p><p class="s4" style="padding-left: 5pt;text-indent: 0pt;line-height: 10pt;text-align: justify;">^<a href="#bookmark19" class="a">(\d+)-.+\.equinix\.com$ for hostname i in figure </a><span class="p">4. For the por-</span></p><p style="padding-left: 5pt;text-indent: 0pt;text-align: justify;"><a href="#bookmark19" class="a">tion that contains the apparent ASN, we extended Hoiho to embed sequences of alphanumeric characters around the ASN delimited by punctuation, in accordance with common operational practice, in the base regexes. For example, regex #2 in figure </a>4 Hoiho em- beds “p” in <span class="s4">^</span>p(\d+)\.[<span class="s4">^</span>\.]+\.equinix\.com$ as “p” appears in the same punctuation-delimited portion as the ASN in hostnames d and f.</p><p style="text-indent: 0pt;text-align: left;"><br/></p></li><li><h2 style="padding-left: 30pt;text-indent: -24pt;text-align: left;"><a name="bookmark14">Merge Regexes</a><a name="bookmark21">&zwnj;</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;"><a href="#bookmark19" class="a">In the second phase, Hoiho examines the set of regexes for each suffix that are very similar, i.e., they differ by a single simple string. For example, the first three regexes in figure </a>4 all have <span class="s4">^ </span>and (\d+)\.[<span class="s4">^</span>\.]+\.equinix\.com$ in common, but regexes #2 and #3 addi- tionally contain the strings “p” and “s”. Hoiho merges these three regexes by embedding an <span class="s18">or </span>statement into the portion of the regex that differs – (?:p|s), so that a single regex will match hostnames with a “p” or “s” prior to the ASN. In this case, regex #1 does not em- bed any characters between the portion of the regex that is in com- mon, indicating these characters are optional. Hoiho represents this optionality by appending a question mark at the end of the <span class="s18">or </span>state- ment – (?:p|s)? – to compose <span class="s4">^</span>(?:p|s)?(\d+)\.[<span class="s4">^</span><a href="#bookmark56" class="a">\.]+\.equinix\.com$. Prior work in Hoiho [</a>19] did not merge similar regexes. This im- provement generalizes when building regexes for alias resolution.</p></li><li><h2 style="padding-left: 30pt;text-indent: -24pt;text-align: left;"><a name="bookmark15">Embed Character Classes</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;"><a href="#bookmark20" class="a">In the third phase, Hoiho identifies character class sequences in common for matched hostnames, replacing the components that exclude specific punctuation built in </a>§3.2 (e.g., [<span class="s4">^</span>\.]+ and [<span class="s4">^</span>-]+) with components that specify character classes. For example, the component [<span class="s4">^</span><a href="#bookmark19" class="a">\.]+ for regex #5 in figure </a>4 matches alphabetical characters for hostnames a-g, although hostname c also contains a digit. Therefore, Hoiho replaces [<span class="s4">^</span><a href="#bookmark56" class="a">\.]+ with [a-z\d]+, which matches a sequence of alphanumeric characters, to build regex #6. This phase is the same as the approach in prior work </a><a href="#bookmark56">[19].</a></p></li><li><h2 style="padding-top: 8pt;padding-left: 30pt;text-indent: -24pt;text-align: left;"><a name="bookmark16">Build Regex Sets</a><a name="bookmark22">&zwnj;</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark19" class="a">In the final phase, Hoiho builds sets of regexes to form a NC in order to increase coverage where the operator uses multiple for- mats. Hoiho ranks regexes by ATP (descending) and evaluates the outcome of combining a regex with each of the regexes below it in the rank order. Hoiho includes an expanded regex in its working set if the ATP is greater than the regex it started with. For example, Hoiho combines regexes #4 and #6 to build NC #7 in figure </a><a href="#bookmark56" class="a">4 because regexes #4 and #6 match different hostname formats. Unlike prior work [</a><a href="#bookmark37" class="a">19] Hoiho does not require the PPV of the new inferences to be similar or better than the PPV of the regex it started with, as our goal is to identify discrepancies between training and embedded ASNs, where the training ASN might be wrong. Appendix </a><a href="#bookmark21" class="a">A dis- cusses the distinction between merging regexes </a><a href="#bookmark22" class="a">(§3.3) and building regex sets </a><a href="#bookmark22">(§3.5).</a></p></li><li><h2 style="padding-top: 8pt;padding-left: 30pt;text-indent: -24pt;text-align: left;"><a name="bookmark17">Select Best Convention</a></h2></li></ol></ol><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;">Hoiho ranks NCs by ATP, and initially select the highest ranked NC as the best, even if a regex below had a higher PPV. Then, Hoiho considers NCs with a lower ATP but expressed in fewer regexes. Hoiho selects a lower-ranked NC if it matches at least as many hostnames as the current best NC, has at least as many TPs, and no more than one additional FP. Because these NCs are made of fewer regexes, there is less opportunity to choose a regex that is the result of over-fitting to the training data.</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p class="s36" style="padding-top: 4pt;padding-left: 47pt;text-indent: 0pt;text-align: left;"><a name="bookmark23">Number of Suffixes with Embedded ASNs</a></p><p class="s36" style="padding-top: 3pt;padding-left: 47pt;text-indent: 0pt;text-align: left;"><a name="bookmark24">Percentage of Interface Classifications</a></p><p class="s36" style="text-indent: 0pt;line-height: 9pt;text-align: right;">0</p><p style="text-indent: 0pt;text-align: left;"><span><img width="189" height="255" alt="image" src="learning_extract_use_asns_files/Image_005.png"/></span></p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;line-height: 9pt;text-align: left;">RTAA</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201007</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201104</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201110</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201207</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201304</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201307</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201404</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201412</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201508</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201603</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201609</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201702</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">bdrmapIT</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201708</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201803</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201901</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201904</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">202001</p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;line-height: 8pt;text-align: left;">PeeringDB</p><p class="s36" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: left;">201709</p><p class="s36" style="padding-left: 20pt;text-indent: 0pt;line-height: 9pt;text-align: left;">202002</p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;text-align: left;">50 100</p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;text-align: left;">150</p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;text-align: left;">200</p><p class="s36" style="padding-top: 2pt;padding-left: 4pt;text-indent: 20pt;line-height: 83%;text-align: left;">Use− Good able</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">12 33</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">16 38</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">17 40</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">14 31</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">12 42</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">15 46</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">22 46</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">19 61</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">13 55</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">16 61</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">19 55</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 9pt;text-align: left;">17 60</p><p class="s36" style="padding-top: 7pt;padding-left: 9pt;text-indent: 0pt;line-height: 9pt;text-align: left;">42 74</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">42 77</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">44 69</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 8pt;text-align: left;">41 80</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 9pt;text-align: left;">55 90</p><p class="s36" style="padding-top: 7pt;padding-left: 9pt;text-indent: 0pt;line-height: 9pt;text-align: left;">36 48</p><p class="s36" style="padding-left: 9pt;text-indent: 0pt;line-height: 9pt;text-align: left;">55 74</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">0</p><p style="text-indent: 0pt;text-align: left;"><span><img width="172" height="255" alt="image" src="learning_extract_use_asns_files/Image_006.png"/></span></p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;line-height: 8pt;text-align: left;">RTAA</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201007</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201104</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201110</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201207</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201304</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201307</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201404</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201412</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201508</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201603</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201609</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201702</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">bdrmapIT</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201708</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201803</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201901</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">201904</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: right;">202001</p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;line-height: 8pt;text-align: left;">PeeringDB</p><p class="s36" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: left;">201709</p><p class="s36" style="padding-left: 20pt;text-indent: 0pt;line-height: 9pt;text-align: left;">202002</p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;line-height: 9pt;text-align: left;">20 40</p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;line-height: 9pt;text-align: left;">60 80</p><p class="s36" style="padding-left: 6pt;text-indent: 0pt;line-height: 9pt;text-align: left;">100</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p class="s36" style="text-indent: 8pt;line-height: 89%;text-align: left;">N @ PPV 0.9k @ 78.5%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">1.3k @ 80.7%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">1.4k @ 77.8%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">1.4k @ 78.7%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">1.8k @ 77.0%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">1.9k @ 80.7%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">2.3k @ 80.0%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">2.6k @ 79.6%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">2.8k @ 74.8%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">3.4k @ 75.7%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">3.4k @ 74.9%</p><p class="s36" style="text-indent: 0pt;line-height: 9pt;text-align: left;">3.8k @ 74.9%</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p class="s36" style="text-indent: 0pt;line-height: 9pt;text-align: left;">4.5k @ 86.3%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">4.5k @ 83.7%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">3.9k @ 83.8%</p><p class="s36" style="text-indent: 0pt;line-height: 8pt;text-align: left;">5.5k @ 83.9%</p><p class="s36" style="text-indent: 0pt;line-height: 9pt;text-align: left;">5.4k @ 87.4%</p><p class="s36" style="padding-top: 7pt;text-indent: 0pt;line-height: 9pt;text-align: left;">3.7k @ 95.9%</p><p class="s36" style="text-indent: 0pt;line-height: 9pt;text-align: left;">6.9k @ 96.0%</p><p style="text-indent: 0pt;text-align: left;"><span><img width="30" height="5" alt="image" src="learning_extract_use_asns_files/Image_007.png"/></span></p><p style="text-indent: 0pt;text-align: left;"><span><img width="29" height="5" alt="image" src="learning_extract_use_asns_files/Image_008.png"/></span></p><p style="text-indent: 0pt;text-align: left;"><span><img width="30" height="5" alt="image" src="learning_extract_use_asns_files/Image_009.png"/></span></p><p style="text-indent: 0pt;text-align: left;"><span><img width="30" height="5" alt="image" src="learning_extract_use_asns_files/Image_010.png"/></span></p><p class="s36" style="padding-top: 5pt;padding-left: 13pt;text-indent: 0pt;text-align: left;">Good Promising Poor Single</p><h3 style="padding-top: 5pt;padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: left;">Figure 5: Classification of NCs. The number of NCs embed- ding ASNs is growing over time.</h3></li><li><h2 style="padding-top: 7pt;padding-left: 22pt;text-indent: -16pt;text-align: left;"><a name="bookmark25">EVALUATING CONVENTIONS</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 3pt;text-align: left;">We applied our method to 17 ITDKs assembled by CAIDA between</p><p class="s36" style="padding-top: 4pt;padding-left: 11pt;text-indent: 0pt;text-align: left;">True Positives Siblings False Positives</p><p style="text-indent: 0pt;text-align: left;"><span><img width="29" height="5" alt="image" src="learning_extract_use_asns_files/Image_011.png"/></span></p><p style="text-indent: 0pt;text-align: left;"><span><img width="30" height="5" alt="image" src="learning_extract_use_asns_files/Image_012.png"/></span></p><p style="text-indent: 0pt;text-align: left;"><span><img width="29" height="5" alt="image" src="learning_extract_use_asns_files/Image_013.png"/></span></p><h3 style="padding-top: 4pt;padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: justify;"><a name="bookmark26">Figure 6: Evaluation of </a><i>usable </i>NCs on training data. The agreement between training and extracted ASNs increases as methods to infer operators improve.</h3><p style="padding-left: 175pt;text-indent: 0pt;line-height: 9pt;text-align: left;">Usable Single</p><p style="padding-left: 18pt;text-indent: 0pt;line-height: 11pt;text-align: left;">Simple – <span class="s4">^</span>as(\d+)\.example\.com$ 17.7% 4.6% Start –</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 6pt;text-align: left;">July 2010 and January 2020 that contain IPv4 routers annotated with</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 3pt;text-align: left;">an ASN inferred with RouterToAsAssignment (RTAA) or bdrmapIT</p><p class="s4" style="padding-left: 32pt;text-indent: 0pt;line-height: 1pt;text-align: left;">^<span class="p">as(\d+)\.[a-z]+\.example\.com$ 50.8% 23.1%</span></p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 11pt;text-align: left;">End – <span class="s4">^</span>[a-z\d]+\.as(\d+)\.example\.com$ 10.8% 43.1%</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 2pt;text-align: left;">Bare</p><p class="s19" style="text-indent: 0pt;line-height: 9pt;text-align: left;">≥</p><p style="text-indent: 0pt;text-align: left;"/><p class="s19" style="text-indent: 0pt;line-height: 9pt;text-align: left;">≥</p><p style="text-indent: 0pt;text-align: left;"/><p style="padding-top: 4pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;">(§2). We also applied our method to two sets of training data that used ASNs recorded by operators in PeeringDB. Hoiho classified a NC as <span class="s18">good </span>if it extracted at least three unique ASNs congruent with training ASNs with a PPV 80%, and a NC as <span class="s18">promising </span>if it extracted at least two unique congruent ASNs with a PPV 50%. The good and promising NCs are <span class="s18">usable </span>because they usually extract a congruent ASN. Hoiho classified a NC as <span class="s18">single </span><a href="#bookmark8" class="a">if it extracted congruent ASNs belonging to a single organization, as in figure </a>2. The remaining NCs with a PPV <span class="s38">&lt; </span>50% are <span class="s18">poor</span>.</p><p class="s19" style="text-indent: 0pt;line-height: 9pt;text-align: left;">≈</p><p style="text-indent: 0pt;text-align: left;"/><p class="s19" style="text-indent: 0pt;line-height: 9pt;text-align: left;">≈</p><p style="text-indent: 0pt;text-align: left;"/><p style="padding-left: 5pt;text-indent: 10pt;line-height: 106%;text-align: right;"><a href="#bookmark23" class="a">Figure </a><a href="#bookmark8" class="a">5 shows that Hoiho classified 12 – 55 NCs per ITDK as good, with the number of good NCs growing over time. The growth of good NCs is a combination of three factors: improvement in heuristic methods, increasing numbers of suffixes that embed ASNs, and an increasing number of VPs that provide visibility of interfaces labeled with ASNs. Hoiho also inferred 55 good NCs for the February 2020 PeeringDB snapshot. Hoiho inferred usable NCs for 206 suffixes across all 19 sets of training data. We obtained ground truth from operators for five NCs we inferred for the January 2020 ITDK. The operators confirmed the regexes reflected their NC, though one (poor) NC was too specific because of stale hostnames. We manually investigated the relationship between the extracted ASNs and the suffixes for the 108 single NCs for the January 2020 ITDK, establishing that 79.5% of the suffixes belonged to the or- ganization with the ASN (e.g. nts.ch in figure </a>2). 82.5% of the 40 single NCs for the February 2020 PeeringDB snapshot are for IXPs that allow the member to assign the hostname for the IXP address, using their own suffix. 12.5% of the suffixes matched a provider, peer, or IXP used by the extracted ASN; for 7.5% the training ASN</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 10pt;text-align: justify;">appeared to coincidentally be the hostname.</p><p style="text-indent: 0pt;line-height: 9pt;text-align: right;">– (\d+)\.[a-z]+\d+\.example\.com$ 5.4% 7.7%</p><p style="text-indent: 0pt;text-align: right;">Complex 15.4% 21.5%</p><h3 style="padding-top: 1pt;padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: justify;">Table 1: Taxonomy of how and where operators embedded ASNs in hostnames. Operators that labeled the neighbor ASN usually placed it at the start of the hostname.</h3><p class="s19" style="text-indent: 0pt;line-height: 9pt;text-align: left;">≈ ≈</p><p style="text-indent: 0pt;text-align: left;"/><p style="padding-top: 5pt;padding-left: 5pt;text-indent: 10pt;line-height: 106%;text-align: right;"><a href="#bookmark24" class="a">Figure </a><a href="#bookmark29" class="a">6 shows the growing congruity between the training ASNs that were heuristically inferred in the ITDK, and ASNs extracted by the usable regexes; the PPV for ASNs inferred using Router- ToAsAssignment is 74.8% – 80.7% and 83.7% – 87.4% for bdrmapIT. Some extracted ASNs differ from their training ASN because the training ASN is a sibling AS of the extracted ASN: including these siblings increased the PPV for RouterToAsAssignment inferences by 1%, and bdrmapIT inferences by 2%. The PPV for the ASNs stored by operators in PeeringDB was 96.0%; we therefore hypothe- size that while some hostnames were stale, more were correct, and these heuristic methods inferred the wrong ASN. In </a>§5, we describe modifications we made to bdrmapIT to incorporate extracted ASNs. The January 2020 ITDK and February 2020 PeeringDB training sets were complementary: in total, we observed 130 usable NCs for different suffixes, with 34 in common – i.e., IXPs observed in both ITDK and PeeringDB, as well as 56 ISPs unique to the ITDK and 40 IXPs unique to PeeringDB. Of the 34 common suffixes, 24 had exactly the same regexes; the 10 that differed varied in specificity, with our method inferring a less specific regex for larger training</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 10pt;text-align: justify;">sets that captured the diversity present in the hostnames.</p><p style="padding-left: 5pt;text-indent: 10pt;text-align: justify;"><a href="#bookmark26" class="a">We characterized how and where operators embedded ASNs in the 130 usable NCs, summarizing our results in table </a>1. An operator with a <span class="s18">simple </span>NC embedded only a neighbor ASN prefaced with “as” in the hostname. The NCs we classified as <span class="s18">start </span>and <span class="s18">end </span>embedded</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="padding-left: 18pt;text-indent: 0pt;line-height: 1pt;text-align: left;"><span><img width="285" height="1" alt="image" src="learning_extract_use_asns_files/Image_014.png"/></span></p><p style="padding-top: 1pt;padding-left: 94pt;text-indent: 2pt;line-height: 106%;text-align: center;"><a name="bookmark27">Correct ASN Incorrect ASN Used Not Used Used Not Used</a></p><table style="border-collapse:collapse;margin-left:18.982pt" cellspacing="0"><tr style="height:15pt"><td style="width:71pt;border-bottom-style:solid;border-bottom-width:1pt"><p style="text-indent: 0pt;text-align: left;"><br/></p></td><td style="width:31pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="padding-left: 4pt;padding-right: 8pt;text-indent: 0pt;text-align: center;">(TP)</p></td><td style="width:36pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="padding-left: 8pt;padding-right: 8pt;text-indent: 0pt;text-align: center;">(FN)</p></td><td style="width:35pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="padding-left: 8pt;padding-right: 8pt;text-indent: 0pt;text-align: center;">(FP)</p></td><td style="width:41pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="padding-left: 8pt;padding-right: 11pt;text-indent: 0pt;text-align: center;">(TN)</p></td></tr><tr style="height:12pt"><td style="width:71pt;border-top-style:solid;border-top-width:1pt"><p class="s39" style="padding-left: 4pt;text-indent: 0pt;line-height: 10pt;text-align: left;">Transit Provider</p></td><td style="width:31pt;border-top-style:solid;border-top-width:1pt"><p class="s39" style="padding-right: 4pt;text-indent: 0pt;line-height: 10pt;text-align: center;">6</p></td><td style="width:36pt;border-top-style:solid;border-top-width:1pt"><p class="s39" style="text-indent: 0pt;line-height: 10pt;text-align: center;">0</p></td><td style="width:35pt;border-top-style:solid;border-top-width:1pt"><p class="s39" style="text-indent: 0pt;line-height: 10pt;text-align: center;">0</p></td><td style="width:41pt;border-top-style:solid;border-top-width:1pt"><p class="s39" style="padding-right: 3pt;text-indent: 0pt;line-height: 10pt;text-align: center;">0</p></td></tr><tr style="height:11pt"><td style="width:71pt"><p class="s39" style="padding-left: 4pt;text-indent: 0pt;line-height: 9pt;text-align: left;">European ISP</p></td><td style="width:31pt"><p class="s39" style="padding-right: 4pt;text-indent: 0pt;line-height: 9pt;text-align: center;">4</p></td><td style="width:36pt"><p class="s39" style="text-indent: 0pt;line-height: 9pt;text-align: center;">0</p></td><td style="width:35pt"><p class="s39" style="text-indent: 0pt;line-height: 9pt;text-align: center;">0</p></td><td style="width:41pt"><p class="s39" style="padding-right: 3pt;text-indent: 0pt;line-height: 9pt;text-align: center;">0</p></td></tr><tr style="height:11pt"><td style="width:71pt"><p class="s39" style="padding-left: 4pt;text-indent: 0pt;line-height: 9pt;text-align: left;">Large ISP</p></td><td style="width:31pt"><p class="s39" style="padding-right: 4pt;text-indent: 0pt;line-height: 9pt;text-align: center;">4</p></td><td style="width:36pt"><p class="s39" style="text-indent: 0pt;line-height: 9pt;text-align: center;">0</p></td><td style="width:35pt"><p class="s39" style="text-indent: 0pt;line-height: 9pt;text-align: center;">2</p></td><td style="width:41pt"><p class="s39" style="padding-left: 8pt;padding-right: 11pt;text-indent: 0pt;line-height: 9pt;text-align: center;">36</p></td></tr><tr style="height:11pt"><td style="width:71pt"><p class="s39" style="padding-left: 4pt;text-indent: 0pt;line-height: 9pt;text-align: left;">Regional US IXP</p></td><td style="width:31pt"><p class="s39" style="padding-right: 4pt;text-indent: 0pt;line-height: 9pt;text-align: center;">6</p></td><td style="width:36pt"><p class="s39" style="text-indent: 0pt;line-height: 9pt;text-align: center;">0</p></td><td style="width:35pt"><p class="s39" style="text-indent: 0pt;line-height: 9pt;text-align: center;">0</p></td><td style="width:41pt"><p class="s39" style="padding-right: 3pt;text-indent: 0pt;line-height: 9pt;text-align: center;">1</p></td></tr><tr style="height:11pt"><td style="width:71pt"><p class="s39" style="padding-left: 4pt;text-indent: 0pt;line-height: 9pt;text-align: left;">Asia-Pacific IXP</p></td><td style="width:31pt"><p class="s39" style="padding-right: 4pt;text-indent: 0pt;line-height: 9pt;text-align: center;">3</p></td><td style="width:36pt"><p class="s39" style="text-indent: 0pt;line-height: 9pt;text-align: center;">1</p></td><td style="width:35pt"><p class="s39" style="text-indent: 0pt;line-height: 9pt;text-align: center;">0</p></td><td style="width:41pt"><p class="s39" style="padding-right: 3pt;text-indent: 0pt;line-height: 9pt;text-align: center;">1</p></td></tr><tr style="height:15pt"><td style="width:71pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="padding-left: 4pt;text-indent: 0pt;line-height: 10pt;text-align: left;">PeeringDB (23)</p></td><td style="width:31pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="padding-left: 4pt;padding-right: 8pt;text-indent: 0pt;line-height: 10pt;text-align: center;">322</p></td><td style="width:36pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="padding-left: 8pt;padding-right: 8pt;text-indent: 0pt;line-height: 10pt;text-align: center;">26</p></td><td style="width:35pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="text-indent: 0pt;line-height: 10pt;text-align: center;">6</p></td><td style="width:41pt;border-bottom-style:solid;border-bottom-width:1pt"><p class="s39" style="padding-left: 8pt;padding-right: 11pt;text-indent: 0pt;line-height: 10pt;text-align: center;">49</p></td></tr></table><p style="padding-left: 23pt;text-indent: 0pt;text-align: left;">Total: 345 27 8 87</p><p style="padding-bottom: 2pt;padding-left: 73pt;text-indent: 0pt;text-align: center;">372 95</p><p style="padding-left: 18pt;text-indent: 0pt;line-height: 1pt;text-align: left;"><span><img width="285" height="1" alt="image" src="learning_extract_use_asns_files/Image_015.png"/></span></p><h3 style="padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: justify;">Table 2: Summary of validation. Our modifications to bdrmapIT made the correct decision for 432 of 467 (92.5%) of extracted ASNs that were incongruent with bdrmapIT’s initial heuristic inference.</h3><p style="padding-top: 5pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;">the neighbor ASN prefaced with “as” at the start or end of the hostname, and embedded additional information in the hostname, such as the bandwidth at which the neighbor is connected, or the name of the neighbor. The NCs we classified as <span class="s18">bare </span>embedded the neighbor ASN but did not preface the ASN with any alphabetic characters. Finally, the NCs we classified as <span class="s18">complex </span>embedded the neighbor ASNs in the middle of the hostname, or used a different annotation other than “as”, or required multiple regexes to capture the convention. Most operators (68.5%) placed the neighbor ASN at the start of the hostname; in contrast, 43.1% of operators that only embedded their own ASN placed it at the end of the hostname.</p></li><li><h2 style="padding-top: 8pt;padding-left: 22pt;text-indent: -16pt;text-align: left;"><a name="bookmark28">USING CONVENTIONS IN bdrmapIT</a><a name="bookmark29">&zwnj;</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;"><a href="#bookmark61" class="a">When processing a router-level graph, bdrmapIT [</a>24] builds topo- logical state for router nodes, annotating each router node with <span class="s18">subsequent ASNs </span>for adjacent routers in traceroute paths, and <span class="s18">desti- nation ASNs </span>for which the router was in a traceroute path. bdrmapIT usually uses the subsequent ASNs to reason about which ASN op- erates a given router. For routers where there were no subsequent routers, bdrmapIT usually uses the destination ASNs to reason about which ASN operates the router. We modified bdrmapIT to evaluate ASNs extracted from hostnames as part of bdrmapIT’s inference approach, to determine if the ASNs appeared reasonable; i.e., were not typos or stale. Our modified bdrmapIT inferred an extracted ASN was reasonable if it matched, or was a sibling of, an ASN in either the subsequent or destination ASN sets, or the extracted ASN is a provider of one of the ASes in these sets.</p><p style="padding-left: 5pt;text-indent: 10pt;line-height: 106%;text-align: justify;">We supplied all of the good, promising, and poor NCs Hoiho inferred from the January 2020 ITDK to our modified bdrmapIT, and then re-processed that ITDK. Compared to the initial ITDK, the agreement between the inferred and extracted ASNs for the routers with ASN annotations increased from 87.4% to 97.1%. and the error rate reduced from 1/7.9 to 1/34.5. Of the 723 router interfaces with ASN mappings different from the ASNs extracted from hostnames, our modified bdrmapIT used the extracted ASN for 526 (72.8%) and was most likely to use ASNs extracted using good NCs than other classes; it used 82.5% of 570 extracted ASNs from good NCs, 44.0% of 109 from promising NCs, and 18.2% of 44 from poor NCs.</p><p style="padding-left: 5pt;text-indent: 9pt;line-height: 106%;text-align: justify;">We obtained ground truth for which ASN operated a given router from five operators, which we used to determine if the hostname</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark27" class="a">contained the correct ASN. We also cross-validated with ASNs recorded by operators in PeeringDB for interface IP addresses with hostnames in 23 different suffixes; we excluded nine router inter- faces where the training ASN, extracted ASN, and ASN in Peer- ingDB were all different, because it was not clear if any of the ASNs were correct. In total, this validation data covered 467 of 723 (64.6%) hostnames where the extracted ASN was different from the ASN initially inferred by bdrmapIT. Our modified bdrmapIT made the correct decision to use the ASN in 92.5% of these hostnames. Ta- ble </a>2 shows that 372 hostnames in our validation data contained the correct ASN, and our modified bdrmapIT used 345 (92.7%) of those hostnames. There were also 95 interfaces with incorrect hostnames in our validation data, and our modified bdrmapIT used eight (8.4%). Five FPs were because the operator recorded their main ASN in PeeringDB (e.g., Microsoft AS8075) but the IXP operator embedded a sibling ASN in the hostname (e.g., Microsoft ASes 8069 or 12076). The extracted ASNs were coincidentally providers of the actual ASN for the remaining three.</p></li><li><h2 style="padding-top: 10pt;padding-left: 22pt;text-indent: -16pt;text-align: left;"><a name="bookmark30">LIMITATIONS</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;"><a href="#bookmark73" class="a">Zhang et al. established in 2006 that because operators do not necessarily maintain hostnames in DNS, Internet topology mapping efforts using hostnames can be distorted [</a><a href="#bookmark29" class="a">37]. Errors in hostnames can impact the accuracy of router ownership inferences using our regexes. Therefore, we recommend that researchers use our regexes in conjunction with topological checks as we did in </a><a href="#bookmark29">§5.</a></p><p style="padding-left: 5pt;text-indent: 9pt;line-height: 106%;text-align: justify;">Our method relies on training data that is usually correct for routers with interfaces in a given suffix – i.e., the training ASNs are usually correct and the hostnames are not stale. Outside of IXPs, where some operators record their public peering interface addresses in PeeringDB, we rely on heuristic-based methods to infer training ASNs. Our method may not infer a usable NC if the heuristic-based methods perform poorly for the routers covered by a suffix, or the hostnames in a suffix are stale.</p></li><li><h2 style="padding-top: 10pt;padding-left: 22pt;text-indent: -16pt;text-align: left;"><a name="bookmark31">FUTURE DIRECTIONS</a></h2></li></ol><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: justify;">We have shown that it is possible to automatically learn regexes that extract ASNs from hostnames, and that we can use these ASNs to improve router ownership inferences that are critical for attribution. A challenging direction for further work is to learn regexes that extract <span class="s18">AS names</span><a href="#bookmark2" class="a">, such as those found in figure </a>1, without relying on a dictionary of AS names. In our preliminary investigation, at least 3x more suffixes embed AS names than AS numbers in hostnames. Obtaining this capability could result in a large, heterogeneous source of validation data, showing exciting promise for evidence- based router ownership inference techniques.</p><p style="padding-left: 5pt;text-indent: 9pt;line-height: 106%;text-align: justify;"><a href="#bookmark66" class="a">Our regexes have also value in identifying router and AS-level interconnections that are not revealed by current measurement in- frastructure. In our preliminary investigation using the OpenINTEL PTR lookup of all delegated IP address space [</a><a href="#bookmark73" class="a">30], we increased the number of hostnames matching a regex inferred from the January 2020 ITDK from 5.4K to 22.5K. While some of these hostnames could be stale [</a><a href="#bookmark42" class="a">37], these hints could inform deployment of new measurement infrastructure to determine which interdomain links exist [</a>3], improving our capability to measure the evolution of the Internet interconnection ecosystem.</p><p style="text-indent: 0pt;text-align: left;"><br/></p><p class="s12" style="padding-top: 7pt;padding-left: 39pt;text-indent: 15pt;line-height: 70%;text-align: left;"><a name="bookmark32">^(?:p|s)?(\d+)\.[a-z\d]+\.equinix\.com$</a><span class="s5"> </span><span class="s40">#7</span><span class="s41"> </span>^(\d+)-.+\.equinix\.com$<a name="bookmark33">&zwnj;</a></p><ol id="l10"><li><p class="s8" style="padding-top: 6pt;padding-left: 51pt;text-indent: -12pt;text-align: justify;"><a name="bookmark34">Ramakrishnan Durairajan, Paul Barford, Joel Sommers, and Walter Willinger. 2015. InterTubes: A Study of the US Long-haul Fiber-optic Infrastructure. In </a><span class="s10">SIGCOMM</span>. 565–578.<a name="bookmark35">&zwnj;</a></p></li><li><p class="s8" style="padding-left: 51pt;text-indent: -12pt;line-height: 5pt;text-align: left;">Ramakrishnan Durairajan, Joel Sommers, and Paul Barford. 2014. Layer 1-</p></li></ol><p class="s12" style="padding-left: 37pt;text-indent: 0pt;line-height: 8pt;text-align: left;">#7a<span class="s5"> </span>^(?:p|s)?(\d+)(?:\.[a-z\d]+|-.+)\.equinix\.com$</p><p class="s12" style="padding-top: 4pt;padding-left: 37pt;text-indent: 18pt;line-height: 15pt;text-align: left;">^(\d+)\.[a-z\d]+\.equinix\.com$<span class="s5"> </span><span class="s34">#7b</span><span class="s35"> </span>^p(\d+)\.[a-z]+\.equinix\.com$</p><p class="s12" style="padding-left: 55pt;text-indent: 0pt;line-height: 5pt;text-align: left;">^s(\d+)\.[a-z]+\.equinix\.com$</p><p class="s12" style="padding-left: 55pt;text-indent: 0pt;text-align: left;">^(\d+)-.+\.equinix\.com$</p><h3 style="padding-top: 3pt;padding-left: 5pt;text-indent: 0pt;line-height: 90%;text-align: justify;"><a href="#bookmark19" class="s42">Figure 7: Equivalent naming conventions (NCs) using the ex- ample routers in figure </a>4. We argue that NC #7 captures the diversity in the hostnames without unnecessary complexity.</h3><h2 style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;text-align: left;"><a name="bookmark36">A MERGING REGEXES VS. REGEX SETS</a><a name="bookmark37">&zwnj;</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: right;"><a href="#bookmark18" class="a">The method described in </a><a href="#bookmark21" class="a">§3 contains two stages that are functionally similar: merging individual regexes that differ by a single simple string </a><a href="#bookmark22" class="a">(§3.3) and building regex sets so that a NC contains multiple regexes each of which match a subset of the hostnames </a><a href="#bookmark19" class="a">(§3.5). For example, NC #7 in figure </a><a href="#bookmark33" class="a">4, duplicated in figure 7, could have been presented differently (e.g. #7a and #7b in figure 7). Our overall goal with Hoiho is to infer regexes that a human might have built, rather than regexes that are either overfitted to the training data, or so complex that a human would have used multiple simpler regexes. At one extreme, we might merge the two regexes that make up NC #7, structuring the functionally different portion in a second or statement, as in NC #7a in figure 7. It is our judgment that NC #7a is one that an operator or user might find difficult to reason about, and that a human building a regex would probably avoid using multiple “or” statements. We suggest that this regex is over-fitted, and in fact the NC is better expressed with two crisp regexes (NC #7), rather than one. At the other extreme, we might present the NC using four individual regexes, as in NC #7b in figure </a><a href="#bookmark19" class="a">7. The first three regexes each individually make minor contributions to NC #7b: using the hostnames in figure </a>4, the first regex extracts three ASNs congruent with training data, while the second and third extract two each. We suggest that the first three regexes in NC #7b are so similar that a human building a regex would probably merge</p><p style="padding-left: 5pt;text-indent: 0pt;line-height: 10pt;text-align: justify;">these three regexes using a single “or” statement.</p><h2 style="padding-top: 7pt;padding-left: 5pt;text-indent: 0pt;text-align: left;"><a name="bookmark38">ACKNOWLEDGMENTS</a></h2><p style="padding-top: 2pt;padding-left: 5pt;text-indent: 0pt;line-height: 106%;text-align: justify;">We thank Young Hyun and Ken Keys for assistance with the ITDK, and the anonymous reviewers for their helpful comments. This work was supported by NSF OAC-1724853, and by the Department of Homeland Security (DHS) Science and Technology Directorate, Cyber Security Division via contract 70RSAT18CB0000013, but this paper represents only the position of the authors.</p><h2 style="padding-top: 6pt;padding-left: 5pt;text-indent: 0pt;text-align: left;"><a name="bookmark39">REFERENCES</a><a name="bookmark40">&zwnj;</a></h2><ol id="l11"><li><p style="padding-left: 21pt;text-indent: -12pt;text-align: left;"><a href="https://www.caida.org/data/internet-topology-data-kit/" class="s9" target="_blank" name="bookmark41">CAIDA. 2020. Macroscopic Internet Topology Data Kit (ITDK). https://www. caida.org/data/internet-topology-data-kit/.</a></p></li><li><p class="s8" style="padding-left: 21pt;text-indent: -12pt;text-align: left;"><a name="bookmark42">Joseph Chabarek and Paul Barford. 2013. What’s in a Name? Decoding Router Interface Names. In </a><span class="s10">HotPlanet</span>. 3–8.</p></li><li><p class="s8" style="padding-left: 21pt;text-indent: -12pt;line-height: 8pt;text-align: left;">Kai Chen, David R. Choffnes, Rahul Potharaju, Yan Chen, Fabian E. Bustamante,</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;text-align: left;"><a name="bookmark43">Dan Pei, and Yao Zhao. 2009. Where the Sidewalk Ends: Extending the Internet AS Graph Using Traceroutes From P2P Users. In </a><span class="s10">CoNEXT</span>. 217–228.</p></li><li><p class="s8" style="padding-left: 21pt;text-indent: -12pt;line-height: 7pt;text-align: left;">Fred J. Damerau. 1964. A Technique for Computer Detection and Correction of</p><p class="s8" style="padding-left: 21pt;text-indent: 0pt;line-height: 8pt;text-align: left;"><a name="bookmark44">Spelling Errors. </a><span class="s10">Commun. ACM </span>7, 3 (March 1964), 171–176.</p></li><li><p class="s8" style="padding-left: 21pt;text-indent: -12pt;text-align: justify;">Amogh Dhamdhere, David D. Clark, Alexander Gamero-Garrido, Matthew Luckie, Ricky K.P. Mok, Gautam Akiwate, Kabir Gogia, Vaibhav Bajpai, Alex C. Snoeren, and k claffy. 2018. Inferring Persistent Interdomain Congestion. In <span class="s10">SIGCOMM</span>. 1–15.</p></li></ol><p class="s8" style="padding-top: 2pt;padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;"><a name="bookmark45">Informed Internet Topology Measurement. In </a><span class="s10">IMC</span>. 381–394.</p><ol id="l12"><li><p class="s8" style="padding-left: 20pt;text-indent: -12pt;text-align: justify;"><a name="bookmark46">Rodérick Fanou, Bradley Huffaker, Ricky Mok, and k claffy. 2020. Unintended Consequences: Effects of Submarine Cable Deployment on Internet Routing. In </a><span class="s10">PAM</span>. 211–227.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -12pt;line-height: 8pt;text-align: justify;">Rodérick Fanou, Francisco Valera, and Amogh Dhamdhere. 2017. Investigating</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;"><a name="bookmark47">the causes of congestion on the african IXP substrate. In </a><span class="s10">IMC</span>. 57–63.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark48">Andrew D. Ferguson, Jordan Place, and Rodrigo Fonseca. 2013. Growth Analysis of a Large ISP. In </a><span class="s10">IMC</span>. 347–352.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 8pt;text-align: left;">Manaf Gharaibeh, Anant Shah, Bradley Huffaker, Han Zhang, Roya Ensafi, and</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;text-align: left;"><a name="bookmark49">Christos Papadopoulos. 2017. A Look at Router Geolocation in Public and Commercial Databases. In </a><span class="s10">IMC</span>. 463–469.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 7pt;text-align: left;">Bradley Huffaker, Amogh Dhamdhere, Marina Fomenkov, and kc claffy. 2010. To-</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;text-align: left;"><a name="bookmark50">ward Topology Dualism: Improving the Accuracy of AS Annotations for Routers. In </a><span class="s10">PAM</span>.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 7pt;text-align: justify;">Bradley Huffaker, Marina Fomenkov, and kc claffy. 2014. DRoP: DNS-based</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;"><a name="bookmark51">Router Positioning. </a><span class="s10">CCR </span>44, 3 (July 2014), 6–13.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark52">Ken Keys, Young Hyun, Matthew Luckie, and k claffy. 2013. Internet-Scale IPv4 Alias Resolution with MIDAR. </a><span class="s10">IEEE/ACM Transactions on Networking </span>21, 2 (April 2013), 383–399.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark53">Vladimir I. Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. </a><span class="s10">Soviet Physics Doklady </span>10, 8 (Feb. 1966), 707–710.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 7pt;text-align: justify;">Matthew Luckie. 2010. Scamper: a Scalable and Extensible Packet Prober for</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;"><a name="bookmark54">Active Measurement of the Internet. In </a><span class="s10">IMC</span>. 239–245.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark55">Matthew Luckie, Robert Beverly, William Brinkmeyer, and k claffy. 2013. Speed- trap: Internet-scale IPv6 Alias Resolution. In </a><span class="s10">IMC</span>. 119–126.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 8pt;text-align: justify;">Matthew Luckie, Amogh Dhamdhere, Bradley Huffaker, David Clark, and k claffy.</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;"><a name="bookmark56">2016. bdrmap: Inference of Borders Between IP Networks. In </a><span class="s10">IMC</span>. 381–396.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark57">Matthew Luckie, Bradley Huffaker, and k claffy. 2019. Learning Regexes to Extract Router Names from Hostnames. In </a><span class="s10">IMC</span>. 337–350.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 8pt;text-align: justify;">Matthew Luckie, Alexander Marder, Marianne Fletcher, Bradley Huffaker, and</p><p style="padding-left: 20pt;text-indent: 0pt;text-align: justify;"><a href="https://www.caida.org/publications/papers/2020/hoiho/" class="s9" target="_blank" name="bookmark58">k claffy. 2020. Data supplement for “Learning to Extract and Use ASNs in Hostnames”. https://www.caida.org/publications/papers/2020/hoiho/.</a></p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark59">Z. Morley Mao, David Johnson, Jennifer Rexford, Jia Wang, and Randy Katz. 2004. Scalable and Accurate Identification of AS-Level Forwarding Paths. In </a><span class="s10">INFOCOM</span>.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 8pt;text-align: justify;">Z. Morley Mao, Jennifer Rexford, Jia Wang, and Randy H. Katz. 2003. Towards</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;"><a name="bookmark60">an accurate AS-level traceroute tool. In </a><span class="s10">SIGCOMM</span>. 365–378.</p></li><li><p style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a href="https://github.com/alexmarder/bdrmapit" class="s9" target="_blank" name="bookmark61">Alexander Marder. 2020. bdrmapIT source code repository. https://github.com/ alexmarder/bdrmapit.</a></p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;">Alexander Marder, Matthew Luckie, Amogh Dhamdhere, Bradley Huffaker, Jonathan M. Smith, and kc claffy. 2018. Pushing the Boundaries with bdrmapIT: Mapping Router Ownership at Internet Scale. In <span class="s10">IMC</span>. 56–69.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 7pt;text-align: justify;">Alexander Marder, Matthew Luckie, Bradley Huffaker, and kc claffy. 2020.</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;"><a name="bookmark62">vrfinder: Finding Outbound Addresses in Traceroute. In </a><span class="s10">SIGMETRICS</span>.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark63">Alexander Marder and Jonathan M. Smith. 2016. MAP-IT: Multipass Accurate Passive Inferences from Traceroute. In </a><span class="s10">IMC</span>. 397–411.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 8pt;text-align: justify;">Ricky K.P. Mok, Vaibhav Bajpai, Amogh Dhamdhere, and k claffy. 2018. Revealing</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 94%;text-align: justify;"><a name="bookmark64">the Load-Balancing Behavior of YouTube Traffic on Interdomain Links. In </a><span class="s10">PAM</span>. 228–240.</p></li><li><p style="padding-left: 20pt;text-indent: -15pt;line-height: 8pt;text-align: justify;"><a href="https://publicsuffix.org/list/" class="s9" target="_blank" name="bookmark65">Mozilla Foundation. 2020. Public Suffix List. https://publicsuffix.org/list/.</a></p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark66">Yibo Pi, Sugih Jamin, Peter Danzig, and Feng Qian. 2020. Latency Imbalance Among Internet Load-Balanced Paths: A Cloud-Centric View. In </a><span class="s10">SIGMETRICS</span>.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 7pt;text-align: justify;">Roland Van Rijswijk-Deij, Mattijs Jonker, Anna Sperotto, and Aiko Pras. 2016.</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;text-align: justify;"><a name="bookmark67">A High-Performance, Scalable Infrastructure for Large-Scale Active DNS Mea- surements. </a><span class="s10">IEEE Journal on Selected Areas in Communication </span>34, 6 (June 2016), 1877–1888.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark68">Quirin Scheitle, Oliver Gasser, Patrick Sattler, and Georg Carle. 2017. HLOC: Hints-Based Geolocation Leveraging Multiple Measurement Frameworks. In </a><span class="s10">TMA</span>.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 94%;text-align: justify;"><a name="bookmark69">Neil Spring, Mira Dontcheva, Maya Rodrig, and David Wetherall. 2004. </a><span class="s10">How to Resolve IP Aliases</span>. UW-CSE-TR 04-05-04.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark70">Neil Spring, Ratul Mahajan, and David Wetherall. 2002. Measuring ISP topologies with Rocketfuel. In </a><span class="s10">SIGCOMM</span>. 133–145.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 8pt;text-align: justify;">Srikanth Sundaresan, Danny Lee, Xiaohong Deng, Yun Feng, and Amogh Dhamd-</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;text-align: justify;"><a name="bookmark71">here. 2017. Challenges in Inferring Internet Congestion Using Throughput Measurements. In </a><span class="s10">IMC</span>. 43–56.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 7pt;text-align: justify;">Bahador Yeganeh, Ramakrishnan Durairajan, Reza Rejaie, and Walter Willinger.</p><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;">2019. How Cloud Traffic Goes Hiding: A Study of Amazon’s Peering Fabric. In</p><p class="s10" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;"><a name="bookmark72">IMC</a><span class="s8">. 202–216.</span></p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;text-align: justify;"><a name="bookmark73">Bahador Yeganeh, Ramakrishnan Durairajan, Reza Rejaie, and Walter Willinger. 2020. A First Comparative Characterization of Multi-cloud Connectivity in Today’s Internet. In </a><span class="s10">PAM</span>. 193–210.</p></li><li><p class="s8" style="padding-left: 20pt;text-indent: -15pt;line-height: 8pt;text-align: justify;">Ming Zhang, Yaoping Ruan, Vivek Pai, and Jennifer Rexford. 2006. How DNS</p></li></ol><p class="s8" style="padding-left: 20pt;text-indent: 0pt;line-height: 8pt;text-align: justify;">Misnaming Distorts Internet Topology Mapping. In <span class="s10">USENIX ATC</span>. 34–39.</p></body></html>
